/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/course-schedule
   @Language: C++
   @Datetime: 19-06-10 17:46
   */

class Solution {
public:
	/*
	 * @param numCourses: a total of n courses
	 * @param prerequisites: a list of prerequisite pairs
	 * @return: true if can finish all courses or false
	 * Tip:
	 * Topological Sort
	 */
	bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites) {
		// write your code here
		unordered_map<int,unordered_set<int> > edges;
		unordered_map<int,int> indegrees;
		for(const auto &edge:prerequisites)
			if(edges[edge.second].insert(edge.first).second)
				++indegrees[edge.first];
		queue<int> que;
		for(int i=numCourses; i--;)
			if(indegrees.count(i)==0) que.push(i);
		for(; que.size(); --numCourses, que.pop())
			for(const auto &node:edges[que.front()])
				if(--indegrees[node]==0) que.push(node);
		return numCourses==0;
	}
};
